package com.celan.year2023.month01.day31;

import java.util.*;

public class Solution {
    public boolean checkXMatrix(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //在对角线上，为0
                //左对角线：i==j
                //右对角线：i == n-j-1
                //不在对角线上，不为0
                if ((((i == j) || (i == n - j - 1)) && grid[i][j] == 0)
                        || (((i != j) && (i != n - j - 1)) && grid[i][j] != 0))
                    return false;
            }
        }
        return true;
    }

    //<旧节点，新节点>
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        return build(head);
    }

    private Node build(Node node) {
        if (node == null) return null;
        //如果cachedNode不存在node，说明node还没有创建
        if (!cachedNode.containsKey(node)) {
            Node newNode = new Node(node.val);
            cachedNode.put(node, newNode);
            newNode.next = build(node.next);
            newNode.random = build(node.random);
        }
        return cachedNode.get(node);
    }


    List<String> res = new ArrayList<>();
    HashSet<String> wordDict = new HashSet<>();
    String s;
    List<String> sentence = new ArrayList<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s;
        this.wordDict.addAll(wordDict);
        backTrack(0);//从0开始
        return res;
    }

    private void backTrack(int idx) {
        if (idx == s.length()) {
            //终止条件，回溯完成后将结果记入结果集
            StringBuilder tmp = new StringBuilder();
            for (String word : sentence) {
                tmp.append(word).append(" ");
            }
            res.add(tmp.toString().trim());
            return;
        }

        //遍历(idx,i)的字符串，是否在wordDict中存在，存在则继续向下回溯
        for (int i = idx; i < s.length(); i++) {
            String word = s.substring(idx, i + 1);
            if (wordDict.contains(word)) {
                sentence.add(word);
                backTrack(i + 1);
                sentence.remove(sentence.size() - 1);
            }
        }
    }


    public int maxPoints(int[][] ps) {
        int n = ps.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            // 由当前点 i 发出的直线所经过的最多点数量
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            //为数字
            if (token.length() > 1 || Character.isDigit(token.charAt(0))) {
                stack.push(Integer.parseInt(token));
            }
            //为符号
            else {
                int left = 0, right = 0;
                if (!stack.isEmpty()) right = stack.pop();
                if (!stack.isEmpty()) left = stack.pop();
                int res = calculate(left, right, token.charAt(0));
                stack.push(res);
            }
        }
        return stack.peek();
    }

    private int calculate(int left, int right, char symbol) {
        int res = 0;
        switch (symbol) {
            case '+':
                res = left + right;
                break;
            case '-':
                res = left - right;
                break;
            case '*':
                res = left * right;
                break;
            case '/':
                res = left / right;
                break;
        }
        return res;
    }

    public int findPeakElement(int[] nums) {
        //你可以假设 nums[-1] = nums[n] = -∞
        int n = nums.length;
        if (n == 1) return 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (isPeak(nums, mid)) return mid;
            //递增->向右边找
            if ((mid < n - 1 && nums[mid] < nums[mid + 1]) || mid == 0) {
                left = mid + 1;
            }
            //递减->向左边找
            if ((mid < n - 1 && nums[mid] > nums[mid + 1]) || mid == n - 1) {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean isPeak(int[] nums, int idx) {
        if (idx == 0) return nums[idx] > nums[idx + 1];
        if (idx == nums.length - 1) return nums[idx] > nums[idx - 1];
        if (nums[idx] > nums[idx + 1] && nums[idx] > nums[idx - 1]) return true;
        return false;
    }
}
